#include <vector>
#include <string>
#include <unordered_map>

using namespace std;


/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


/**
 * 给定一棵二叉树 root，返回所有重复的子树。
 * 对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 * 如果两棵树具有相同的结构和相同的结点值，则它们是重复的。
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-duplicate-subtrees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        unordered_map<string, int> table;

        vector<TreeNode*> res;
        serializeHelper(root, table, res);  // use preorder traversal
        return res;
    }

private:
    string serializeHelper(TreeNode* root, unordered_map<string, int>& table, vector<TreeNode*>& res) {
        string str;
        if (!root) {
            str += "None,";
        } else {
            str += to_string(root->val) + ",";
            str += serializeHelper(root->left, table, res);
            str += serializeHelper(root->right, table, res);
            table[str]++;
            if (table[str] == 2) res.push_back(root);  // 第一次发现重复时加入答案
        }
        return str;
    }
};
